#ifndef __PRIORITYQUEUE_MY__IMPL___
#define __PRIORITYQUEUE_MY__IMPL___
#include<vector>
#include<stdio.h>

#define DEFAULT_INITIAL_CAPACITY 1000
const unsigned int MAX_ARRAY_SIZE=0x7ffffff0;

class QueueComparator{
public:
	virtual int compareTo(void*lhs, void*rhs)=0;
};


template <class T>
class PriorityQueue{
public:
    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    T* queue;
	int queueLength;

    /**
     * The number of elements in the priority queue.
     */
    int size;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
    QueueComparator*comparator;
    /**
     * The number of times this priority queue has been
     * <i>structurally modified</i>.  See AbstractList for gory details.
     */
    int modCount;

	PriorityQueue() {
       init(100,NULL);
    }

	PriorityQueue(int initialCapacity,
                         QueueComparator*comparator) {
       init(initialCapacity,comparator);
    }

	void init(int initialCapacity,
                         QueueComparator*comparator){
		// Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw "Initial capacity should not be less zero";
        this->queue = new T[initialCapacity];
		queueLength=initialCapacity;
        this->comparator = comparator;
		size=0;
		modCount=0;
	}

	~PriorityQueue(){
		delete [] queue;
	}

    

    /**
     * Increases the capacity of the array.
     *
     * @param minCapacity the desired minimum capacity
     */
    void grow(int minCapacity) {
		int oldCapacity = queueLength;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
		
		T*nqueue = copyOfArray(queue, queueLength, newCapacity);
		delete[]queue;
		queue=nqueue;
		queueLength=newCapacity;
    }

	T*copyOfArray(T*arr,int oldLength, int newLength){
		T*newarray=new T[newLength];
		int minLength=oldLength<newLength?oldLength:newLength;
		for(int i=0;i<minLength;i++){
			newarray[i]=arr[i];
		}
		if(newLength>oldLength){
			int difference=newLength-oldLength;
			for(int i=0;i<difference;i++){
				newarray[i+minLength]=NULL;
			}
		}
		return newarray;
	}

	

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    bool add(T e) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    bool offer(T e) {
        if (e == NULL)
            throw "Null Pointer exception";
        modCount++;
        int i = size;
        if (i >= queueLength)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

    T peek() {
        if (size == 0)
            return NULL;
        return (T*) queue[0];
    }

    int indexOf(T o) {
        if (o != NULL) {
            for (int i = 0; i < size; i++)
                if (o==queue[i])
                    return i;
        }

        return -1;
    }

    /**
     * Removes a single instance of the specified element from this queue,
     * if it is present.  More formally, removes an element {@code e} such
     * that {@code o.equals(e)}, if this queue contains one or more such
     * elements.  Returns {@code true} if and only if this queue contained
     * the specified element (or equivalently, if this queue changed as a
     * result of the call).
     *
     * @param o element to be removed from this queue, if present
     * @return {@code true} if this queue changed as a result of the call
     */
    bool remove(T o) {
        int i = indexOf(o);
        if (i == -1)
            return false;
        else {
            removeAt(i);
            return true;
        }
    }

    /**
     * Version of remove using reference equality, not equals.
     * Needed by iterator.remove.
     *
     * @param o element to be removed from this queue, if present
     * @return {@code true} if removed
     */
    bool removeEq(T o) {
        for (int i = 0; i < size; i++) {
            if (o == queue[i]) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    /**
     * Returns {@code true} if this queue contains the specified element.
     * More formally, returns {@code true} if and only if this queue contains
     * at least one element {@code e} such that {@code o.equals(e)}.
     *
     * @param o object to be checked for containment in this queue
     * @return {@code true} if this queue contains the specified element
     */
    bool contains(T o) {
        return indexOf(o) != -1;
    }

    int getSize() {
        return size;
    }

    /**
     * Removes all of the elements from this priority queue.
     * The queue will be empty after this call returns.
     */
    void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            queue[i] = NULL;
        size = 0;
    }

    T poll() {
        if (size == 0)
            return NULL;
        int s = --size;
        modCount++;
        T result = (T) queue[0];
        T x = (T) queue[s];
        queue[s] = NULL;
        if (s != 0){
            siftDown(0, x);
		}
        return result;
    }

	T*getValues(){
		return queue;
	}

    /**
     * Removes the ith element from queue.
     *
     * Normally this method leaves the elements at up to i-1,
     * inclusive, untouched.  Under these circumstances, it returns
     * null.  Occasionally, in order to maintain the heap invariant,
     * it must swap a later element of the list with one earlier than
     * i.  Under these circumstances, this method returns the element
     * that was previously at the end of the list and is now at some
     * position before i. This fact is used by iterator.remove so as to
     * avoid missing traversing elements.
     */
    T removeAt(int i) {
        assert i >= 0 && i < size;
        modCount++;
        int s = --size;
        if (s == i){ // removed last element
            queue[i] = null;
		}else {
            T moved = (T*) queue[s];
            queue[s] = null;
            siftDown(i, moved);
            if (queue[i] == moved) {
                siftUp(i, moved);
                if (queue[i] != moved)
                    return moved;
            }
        }

        return NULL;
    }

    /**
     * Inserts item x at position k, maintaining heap invariant by
     * promoting x up the tree until it is greater than or equal to
     * its parent, or is the root.
     *
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    void siftUp(int k, T x) {
        if (comparator != NULL)
            siftUpUsingComparator(k, x);
        else
            throw "Please set comparator to priority queue";
    }

    void siftUpUsingComparator(int k, T x) {
        while (k > 0) {
            int parent = (unsigned int)(k - 1) >> 1;
            T e = (T)queue[parent];
            if (comparator->compareTo((void*)&(*x), (void*)(&(*((T) e)))) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }

        queue[k] = x;
    }

    /**
     * Inserts item x at position k, maintaining heap invariant by
     * demoting x down the tree repeatedly until it is less than or
     * equal to its children or is a leaf.
     *
     * @param k the position to fill
     * @param x the item to insert
     */
    void siftDown(int k, T x) {
        if (comparator != NULL)
            siftDownUsingComparator(k, x);
        else
            throw "Please set comparator to priority queue";
    }

    void siftDownUsingComparator(int k, T x) {
        int half = ((unsigned int)size) >> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            T c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator->compareTo((void*)&(*c), (void*)&(*(queue[right]))) > 0)
                c = queue[child = right];
            if (comparator->compareTo((void*)&(*x), (void*)&(*((T) c))) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

    /**
     * Establishes the heap invariant (described above) in the entire tree,
     * assuming nothing about the order of the elements prior to the call.
     */
    void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (T) queue[i]);
    }

    /**
     * Returns the comparator used to order the elements in this
     * queue, or {@code null} if this queue is sorted according to
     * the {@linkplain Comparable natural ordering} of its elements.
     *
     * @return the comparator used to order this queue, or
     *         {@code null} if this queue is sorted according to the
     *         natural ordering of its elements
     */
    QueueComparator* getComparator() {
        return comparator;
    }

	void setComparator(QueueComparator*comparator) {
        this->comparator=comparator;
    }
};

#endif